package com.java.tree;

/**
 * 线索化二叉树
 *
 * @author 19252
 * @date 2020/7/24
 */
public class ThreadedBinaryTreeDemo {

    public static void main(String[] args) {

        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
        Node node1 = new Node(1, "宋江");
        Node node2 = new Node(2, "卢俊义");
        Node node3 = new Node(3, "吴用");
        Node node4 = new Node(4, "公孙胜");
        Node node5 = new Node(5, "关胜");
        Node node6 = new Node(6, "林冲");
        Node node7 = new Node(7, "秦明");
        Node node8 = new Node(8, "呼延灼");
        threadedBinaryTree.addNode(node7);
        threadedBinaryTree.addNode(node2);
        threadedBinaryTree.addNode(node1);
        threadedBinaryTree.addNode(node3);
        threadedBinaryTree.addNode(node4);
        threadedBinaryTree.addNode(node5);
        threadedBinaryTree.addNode(node6);
        threadedBinaryTree.addNode(node8);
        // 前序遍历
        threadedBinaryTree.preOrder();
        // 前序线索化二叉树
        threadedBinaryTree.preThreadedNodes();
        // 前序线索化二叉树的验证
        System.out.println("前序线索化验证~~~");
        System.out.println(node4.getLeft());
        System.out.println(node4.getRight());
        System.out.println("前序线索化二叉树的遍历");
        threadedBinaryTree.preThreadedShowNodes();
        // threadedBinaryTree.infixOrder();
        // 中序线索化二叉树的验证
        /*threadedBinaryTree.threadedNodes();
        System.out.println("node8 的线索化的右结点" + node8.getRight());
        System.out.println("node8 的线索化的左结点" + node8.getLeft());
        System.out.println("线索化二叉树的遍历");
        threadedBinaryTree.threadedShowNodes();*/
    }
}

/**
 * 线索化二叉树的实现
 */
class ThreadedBinaryTree {

    /**
     * 根节点
     */
    private Node root;

    /**
     *
     */
    public Node preNode = null;

    public Node getRoot() {
        return root;
    }

    public void setRoot(Node root) {
        this.root = root;
    }

    public Node getPreNode() {
        return preNode;
    }

    public void setPreNode(Node preNode) {
        this.preNode = preNode;
    }

    /**
     * 向二叉树中添加结点
     * 按照大小顺序向二叉树中添加结点左边为小于该结点的结点，右边为大于该结点的结点
     *
     * @param node 二叉树的结点
     */
    public void addNode(Node node) {
        Node temp = this.root;
        if (temp == null) {
            this.root = node;
        } else {
            while (true) {
                // 重复添加判断
                if (node.getNo() == temp.getNo()) {
                    System.out.printf("您要添加的 %d 结点已存在！\n", temp.getNo());
                    break;
                }
                // 当前要添加的结点小于root结点，则向左添加
                if (node.getNo() < temp.getNo()) {
                    // 当前的结点的左子结点不为空
                    if (temp.getLeft() != null) {
                        // 就将当前节点变为当前结点的左子结点
                        // 再重新开始比较
                        temp = temp.getLeft();
                    } else {
                        // 完成加入树的操作退出
                        temp.setLeft(node);
                        break;
                    }
                }
                // 当前要添加的结点大于root结点，则向右添加
                if (node.getNo() > temp.getNo()) {
                    if (temp.getRight() != null) {
                        temp = temp.getRight();
                    } else {
                        temp.setRight(node);
                        break;
                    }
                }
            }
        }
    }

    /**
     * 前序遍历
     */
    public void preOrder(){
        this.root.preOrder();
    }

    /**
     * 中序遍历
     */
    public void infixOrder() {
        this.root.infixOrder();
    }

    /**
     * 前序线索化二叉树方法重写
     */
    public void preThreadedNodes(){
        preThreadedNodes(this.root);
    }

    /**
     * 前序线索化二叉树
     * @param node 当前结点
     */
    public void preThreadedNodes(Node node){
        if (node == null){
            return;
        }
        // 在线索化结点的左指针前，保存左指针的状态
        boolean leftFlag = true;
        if (node.getLeft() == null){
            leftFlag = false;
        }
        // 线索化当前结点
        if (node.getLeft() == null){
            node.setLeft(preNode);
            node.setLeftType(1);
        }
        if (preNode != null && preNode.getRight() == null){
            preNode.setRight(node);
            preNode.setRightType(1);
        }
        preNode = node;
        if (leftFlag){
            preThreadedNodes(node.getLeft());
        }
        preThreadedNodes(node.getRight());
    }


    /**
     *
     */
    public void preThreadedShowNodes(){
        Node node = this.root;
        if (node == null){
            System.out.println("二叉树为空");
            return;
        }
        // 输出根结点
        while (true){
            // 寻找二叉树最左边的结点
            while (node.getLeft() != null && node.getLeftType() == 0){
                // 不是最左边的结点，而是正常的左结点输出
                System.out.println(node);
                node = node.getLeft();
            }
            // 找到最左边的结点输出
            // 再判断下一个结点是否有右结点
            while (node.getRightType() == 1){
                System.out.println(node);
                node = node.getRight();
            }
            // 线索化遍历结束
            if (node.getLeft() != null && node.getRight() == null){
                System.out.println(node);
                break;
            }
            // 对于没有左结点但存在右结点的直接输出右结点，
            // 线索化遍历的条件与当前的条件相仿，所以要先判断是否结束
            if (node.getLeftType() == 1 && node.getRightType() == 0){
                System.out.println(node);
                node = node.getRight();
            }

        }
    }



    /**
     * 线索化遍历方法的重写
     */
    public void threadedNodes(){
        threadedNodes(this.root);
    }

    /**
     * 对二叉树进行中序线索化的方法
     *
     * @param node 当前需要线索化的结点
     */
    public void threadedNodes(Node node) {
        // 结点为空，不能线索化
        if (node == null) {
            return;
        }
        // 线索化左子树
        threadedNodes(node.getLeft());

        // 处理当前结点的前驱结点
        if (node.getLeft() == null) {
            // 让当前结点的左指针指向前去结点
            node.setLeft(preNode);
            // 修改当前结点的左指针类型，指向前驱结点
            node.setLeftType(1);
        }
        // 处理后继结点
        if (preNode != null && preNode.getRight() == null) {
            // 让前驱结点的右指针指向当前节点
            preNode.setRight(node);
            // 修改前驱结点的右指针类型
            preNode.setRightType(1);
        }
        // 每处理一个结点后，让当前结点是下一个结点的前驱结点
        preNode = node;

        // 线索化右子树
        threadedNodes(node.getRight());
    }

    /**
     * 中序遍历
     * 对已经完成线索化的二叉树进行遍历（原先的递归遍历方法已经不适用了）
     */
    public void threadedShowNodes(){
        // 从根结点开始
        Node node = this.root;
        boolean flag = true;
        while (flag){
            // node.getLeftType() == 0 代表node 还不是一个二叉树中的最左边的子结点
            while (node.getLeftType() == 0) {
                node = node.getLeft();
            }
            // 找到最左边的子结点第一个结点输出
            System.out.println(node);
            // 输出父结点
            while (node.getRightType() == 1) {
                // 输出后继结点
                node = node.getRight();
                // 如果父结点没有右结点，就会继续输出
                System.out.println(node);
            }
            node = node.getRight();
            // 二叉树最下层的最右边的结点有前驱结点但没有后继结点，此时退出输出
            if (node.getLeft() != null && node.getRight() == null){
                System.out.println(node);
                flag = false;
            }
        }

    }

}

/**
 * 结点
 */
class Node {

    /**
     * no 排名
     */
    private int no;

    /**
     * 姓名
     */
    private String name;

    /**
     * 左结点
     */
    private Node left;

    /**
     * 右结点
     */
    private Node right;

    /**
     * leftType == 0 表示指向的是左子树
     * leftType == 1 表示指向的是前驱结点
     */
    private int leftType;

    /**
     * rightType == 0 表示指向的是右子树
     * rightType == 1 表示指向的是后继结点
     */
    private int rightType;


    public Node() {
    }

    public Node(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }


    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    public void preOrder(){
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }
}


